from decisionTree import *
import random
from math import log2


# The agent receives a dictionary as percept that contains the different attributes as
# keys values to the attributes. I wanted to make more explicit what the different values
# mean, therefore I introduced this form of class attributes as more speaking representatives
# of the different values.
class PerceptValue:
    # Class variables for the types of object that can be contained in a cell
    # as well as for the energy level
    Grass, Dirt, Wheat, Seed = range(0, 4)
    High, Ok, Low = range(0, 3)

 

# The class is a stub of what you should use to implement your decision maker.
class AI():

    # The actions that an agent can take (duplicated from simulation.py)
    # the reason function shall return one of these!
    WalkEast, WalkWest, WalkNorth, WalkSouth, DoHarvest, DoRest, DoSow = range(0, 7)

    def RandomDirection(self):
        rDraw = random.randrange(0, 5)
        if rDraw == 0:
            return AI.WalkEast
        elif rDraw == 1:
            return AI.WalkNorth
        elif rDraw == 2:
            return AI.WalkWest
        elif rDraw == 3:
            return AI.WalkSouth
        else:
            return AI.DoRest


    def __init__(self):
        self.manualControl = False
        # if you want your agent to execute the action that you
        # return, then you have to say False here. Otherwise, anything
        # you return will be overwritten by the manual input of the human.
        self.Age = 0
        self.table = []
        self.attributes = {'onMyPosition':1,'onCellNorth':2,'onCellEast':3,
               'onCellSouth':4,'onCellWest':5,'myEnergy':6}
        if(not(self.manualControl)):
            self.table = self.ReadFromFile('treefile.txt')
            self.myTree = self.ID3(self.table,self.attributes)
            self.myTree.display()
        
        # this is just a dummy variable to show to you that the AI can
        # use an internal data structue, e.g. containing a decision tree
        # a knowledge base out of rules, etc.
        # if you want to test your hand-made decision tree, you may
        # generate and fill it here
       
        #self.myTree = DecisionFork("onMyPosition",
        #    {PerceptValue.Seed: DecisionLeaf(AI.DoRest),
        #    PerceptValue.Dirt: DecisionLeaf(AI.DoSow),
        #    PerceptValue.Wheat: DecisionLeaf(AI.DoHarvest),
        #    PerceptValue.Grass: DecisionFork("onCellNorth", 
        #            {PerceptValue.Wheat:DecisionLeaf(AI.WalkNorth),
        #             PerceptValue.Dirt:DecisionFork("onCellEast",
        #                        {PerceptValue.Wheat:DecisionLeaf(AI.WalkEast),
        #                         PerceptValue.Dirt:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.DoRest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.DoRest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.DoRest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.DoRest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.DoRest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.DoRest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Grass:DecisionFork("onCellSouth",{
        #                                PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Seed:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 })
        #                         }),
        #             PerceptValue.Grass:DecisionFork("onCellEast",
        #                        {PerceptValue.Wheat:DecisionLeaf(AI.WalkEast),
        #                         PerceptValue.Dirt:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Grass:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Seed:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 })
        #                         }),
        #             PerceptValue.Seed:DecisionFork("onCellEast",
        #                        {PerceptValue.Wheat:DecisionLeaf(AI.WalkEast),
        #                         PerceptValue.Dirt:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Grass:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Seed:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 })
        #                         })}
        #                    )})



        #self.myTree = DecisionFork("ground",
        #    {PerceptValue.Dirt: DecisionLeaf(AI.DoSow),
        #    PerceptValue.Wheat: DecisionLeaf(AI.DoHarvest),
        #    PerceptValue.Seed: DecisionFork("onCellNorth", 
        #            {PerceptValue.Wheat:DecisionLeaf(AI.WalkNorth),
        #             PerceptValue.Dirt:DecisionFork("onCellEast",
        #                        {PerceptValue.Wheat:DecisionLeaf(AI.WalkEast),
        #                         PerceptValue.Dirt:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Grass:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Seed:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 })
        #                         }),
        #             PerceptValue.Grass:DecisionFork("onCellEast",
        #                        {PerceptValue.Wheat:DecisionLeaf(AI.WalkEast),
        #                         PerceptValue.Dirt:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Grass:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Seed:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 })
        #                         }),
        #             PerceptValue.Seed:DecisionFork("onCellEast",
        #                        {PerceptValue.Wheat:DecisionLeaf(AI.WalkEast),
        #                         PerceptValue.Dirt:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Grass:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Seed:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 })
        #                         })
        #             }),
        #    PerceptValue.Grass: DecisionFork("onCellNorth", 
        #            {PerceptValue.Wheat:DecisionLeaf(AI.WalkNorth),
        #             PerceptValue.Dirt:DecisionFork("onCellEast",
        #                        {PerceptValue.Wheat:DecisionLeaf(AI.WalkEast),
        #                         PerceptValue.Dirt:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Grass:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Seed:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 })
        #                         }),
        #             PerceptValue.Grass:DecisionFork("onCellEast",
        #                        {PerceptValue.Wheat:DecisionLeaf(AI.WalkEast),
        #                         PerceptValue.Dirt:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Grass:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Seed:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 })
        #                         }),
        #             PerceptValue.Seed:DecisionFork("onCellEast",
        #                        {PerceptValue.Wheat:DecisionLeaf(AI.WalkEast),
        #                         PerceptValue.Dirt:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Grass:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 }),
        #                         PerceptValue.Seed:DecisionFork("onCellSouth",
        #                                {PerceptValue.Wheat:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Dirt:DecisionLeaf(AI.WalkSouth),
        #                                 PerceptValue.Grass:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     }),
        #                                 PerceptValue.Seed:DecisionFork("onCellWest",
        #                                    {PerceptValue.Dirt:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Grass:DecisionLeaf(self.RandomDirection()),
        #                                     PerceptValue.Seed:DecisionLeaf(AI.WalkWest),
        #                                     PerceptValue.Wheat:DecisionLeaf(AI.WalkWest)
        #                                     })
        #                                 })
        #                         })}
        #                    )})
        
        
        
    # This function is called by the agent's update function. it gets the
    # sensor data in form of a percept dictionary (there is a new one generated
    # for every tick. the dictionary has the form:
    # {"onMyPosition" : <value>, "onCellNorth" : <value>, "onCellEast" : <value>, "onCellSouth" : <value>, "onCellWest" : <value>, "myEnergy" : <value>}
    # the range of the values is given by PerceptValue.Grass ,....
    # the first 5 attributes describe what is the cell on the agent' position and on the cells around, the last describes the energy level 
    # This function shall return an action.
    def runDecisionTree(self, nodeType, percept):
        
        if(isinstance(nodeType,DecisionLeaf)):
            return nodeType
        elif(isinstance(nodeType,DecisionFork)):
            #choice = {}
            #choice[nodeType.attribute] = percept[nodeType.attribute]
            return self.runDecisionTree(nodeType.get(percept),percept)

    def reason(self, percept):
        # This is a simple if construct that should serve as an _example_ only
        # to show what you get and how you return actions. This you need to fill with 
        # a function that parses a decision tree! 
        # here you see how to use the speaking class attributes of the PerceptValue Class.
        #if percept["onMyPosition"] == PerceptValue.Wheat:
            #return AI.DoHarvest
        #elif percept["onMyPosition"] == PerceptValue.Dirt:
            #return AI.DoSow
        #else:
            #rDraw = random.randrange(0, 5)
            #if rDraw == 0:
                #return AI.WalkEast
        #    elif rDraw == 1:
        #        return AI.WalkNorth
        #    elif rDraw == 2:
        #        return AI.WalkWest
        #    elif rDraw == 3:
        #        return AI.WalkSouth
        #    else:
        #        return AI.DoRest
        #return None

        #choice = {}
        #choice["ground"] = percept["onMyPosition"]
        #choice["ground"] = PerceptValue.Grass

        #temp = self.myTree.get(choice)

        #svar1,svar2 = self.CheckForSame(self.testTable)
        #choice[myTree.attribute] = percept[myTree.attribute]
        svar = self.runDecisionTree(self.myTree.get(percept),percept)
        return svar.result




    # This function is called by the agent's manualAction function for
    # informing you about the user's selected action in a particular situation
    # expressed by the percept. You need to extend this function for solving 
    # task b. Currently it contains a stub that simply prints everything to 
    # demonstrate that it is automatically called.
    def notify(self, tick, percept, action):
        f = open('treefile.txt', 'a')
        #print(tick,  ": ",
            #percept.typeOn, ", ",
            #percept.typeNorth, ", ",
            #percept.typeEast, ", ",
            #percept.typeSouth, ", ",
            #percept.typeWest, ", ",
            #percept.energyLevel, ": ",
            #self.toString(action))
        row = [action,percept['onMyPosition'],percept['onCellNorth'],percept['onCellEast'],
               percept['onCellSouth'],percept['onCellWest'],percept['myEnergy']]
        for value in row:
            f.write('%d,'%value)
        f.write('\n')
        self.table += [row]
        print(percept)
        f.close()

    def ReadFromFile(self,filename):
        table = []
        f = open(filename)
        for line in f.readlines():
            row = []
            commalist = line[:-2]
            list = commalist.split(',')
            for element in list:
                row.append(int(element))
            table += [row]
            
        f.close()
        return table


    def ID3(self, examples, attributes):
        same, action = self.CheckForSame(examples)
        if(same):
            print("DecisionLeaf", action)
            return DecisionLeaf(action)
        empty, action = self.CheckForEmpty(examples,attributes)  
        if(empty):
            print("DecisionLeaf", action)
            return DecisionLeaf(action)

        Values, A = self.Calculate(examples, attributes)
        print("DecisionFork: ", A)
        Tree = DecisionFork(A,{})
        for vi in Values[A]:
            #print("Value: ",vi," Attribute: ",A)
            examples_vi = self.GetSubTable(A, vi, examples, attributes)
            if(len(examples_vi) ==0 ):
                Tree.add(vi, DecisionLeaf(self.MostCommon(examples)))
                print("DecisionLeaf")
            else:
                Tree.add(vi, self.ID3(examples_vi,self.RemoveAttribute(attributes,A)))
        return Tree

    def RemoveAttribute(self, attributes, A):

        copy = attributes.copy()
        if A in copy:
            del copy[A]
        return copy


    def GetSubTable(self, A, vi, examples, attributes):
        subtable = []
        for example in examples:
            if(example[self.attributes[A]] == vi):
                subtable.append(example)
        return subtable

    def MostCommon(self,examples):
        walkEast = walkWest = walkNorth = walkSouth = DoHarvest = DoRest = DoSow = 0
        for example in examples:
            if example[0] == 0:
                walkEast += 1
            if example[0] == 1:
                walkWest += 1
            if example[0] == 2:
                walkNorth += 1
            if example[0] == 3:
                walkSouth += 1
            if example[0] == 4:
                DoHarvest += 1
            if example[0] == 5:
                DoRest += 1
            if example[0] == 6:
                DoSow += 1
        #List =[walkEast,walkWest,walkNorth,walkSouth,DoHarvest,DoRest,DoSow]
        #return max(List)
        List ={0 : walkEast, 1 : walkWest, 2 : walkNorth, 3 : walkSouth, 4 : DoHarvest, 5: DoRest, 6 : DoSow}
        var = max(List,key = lambda x: List[x])            
        return var

    #testTable = [[1,1],[1,1],[1,1],[1,1]]

    def CheckForSame(self, Examples):
        issame = True
        old = Examples[0][0]
        for example in Examples:
            new = example[0]
            if(new != old):
                issame = False
                old = new
        if(issame):
            return True,old
        else:
            return False,old

    def CheckForEmpty(self, examples, attributes):
        if (len(attributes) == 0):
            walkEast = walkWest = walkNorth = walkSouth = DoHarvest = DoRest = DoSow = 0
            for example in examples:
                if example[0] == 0:
                    walkEast += 1
                if example[0] == 1:
                    walkWest += 1
                if example[0] == 2:
                    walkNorth += 1
                if example[0] == 3:
                    walkSouth += 1
                if example[0] == 4:
                    DoHarvest += 1
                if example[0] == 5:
                    DoRest += 1
                if example[0] == 6:
                    DoSow += 1
            #List =[walkEast,walkWest,walkNorth,walkSouth,DoHarvest,DoRest,DoSow]
            List ={0 : walkEast, 1 : walkWest, 2 : walkNorth, 3 : walkSouth, 4 : DoHarvest, 5: DoRest, 6 : DoSow}
            var = max(List,key = lambda x: List[x])            
            #return var
            return True, var
        else:
            return False, 0

    



    def Calculate(self,examples,attributes):

        HS = self.CalculateIG(examples)
        HSDict = {}
        subTableGrass = []
        subTableDirt = []
        subTableSeed = []
        subTableWheat = []
        subTableOk = []
        subTableLow = []
        subTableHigh = []

        for attribute in attributes:
            
            if(attribute == 'myEnergy'):
                for example in examples:
                    if(example[attributes[attribute]] == PerceptValue.High):
                        subTableHigh += [example]
                    elif(example[attributes[attribute]] == PerceptValue.Ok):
                        subTableOk += [example]
                    elif(example[attributes[attribute]] == PerceptValue.Low):
                        subTableLow += [example]

                TotalRows = len(examples)
                HighIG = self.CalculateIG(subTableHigh)
                OkIG = self.CalculateIG(subTableOk)
                LowIG = self.CalculateIG(subTableLow);
                HSDict[attribute] = HS - (len(subTableHigh)/TotalRows*HighIG +
                                 len(subTableOk)/TotalRows*OkIG +
                                 len(subTableLow)/TotalRows*LowIG)
            else:
                for example in examples:
                    if(example[attributes[attribute]] == PerceptValue.Grass):
                        subTableGrass += [example]
                    elif(example[attributes[attribute]] == PerceptValue.Dirt):
                        subTableDirt += [example]
                    elif(example[attributes[attribute]] == PerceptValue.Seed):
                        subTableSeed += [example]
                    elif(example[attributes[attribute]] == PerceptValue.Wheat):
                        subTableWheat += [example]

                TotalRows = len(examples)
                GrassIG = self.CalculateIG(subTableGrass)
                DirtIG = self.CalculateIG(subTableDirt)
                SeedIG = self.CalculateIG(subTableSeed)
                WheatIG = self.CalculateIG(subTableWheat)
                HSDict[attribute] = HS - (len(subTableGrass)/TotalRows*GrassIG +
                                 len(subTableDirt)/TotalRows*DirtIG +
                                 len(subTableSeed)/TotalRows*SeedIG +
                                 len(subTableWheat)/TotalRows*WheatIG)

            subTableGrass.clear()
            subTableDirt.clear()
            subTableSeed.clear()
            subTableWheat.clear()
            subTableHigh.clear()
            subTableOk.clear()
            subTableLow.clear()

        var = max(attributes,key = lambda x: HSDict[x])
        Values = {}
        if(var == 'myEnergy'):
            List = [0,1,2]
        else:
            List = [0,1,2,3]
        Values[var] = List
        return Values, var



    def CalculateIG(self,examples):
        numberOfRows = len(examples)

        WalkEast = WalkWest = WalkNorth = WalkSouth = DoHarvest = DoRest = DoSow = 0
        for example in examples:
            if(example[0] == 0):
                WalkEast += 1
            elif(example[0] == 1):
                WalkWest += 1
            elif(example[0] == 2):
                WalkNorth += 1
            elif(example[0] == 3):
                WalkSouth += 1
            elif(example[0] == 4):
                DoHarvest += 1
            elif(example[0] == 5):
                DoRest += 1
            else:
                DoSow += 1

        IG = (
              -self.IGHelper(WalkEast,numberOfRows)
              -self.IGHelper(WalkWest,numberOfRows)
              -self.IGHelper(WalkNorth,numberOfRows)
              -self.IGHelper(WalkSouth,numberOfRows)
              -self.IGHelper(DoHarvest,numberOfRows)
              -self.IGHelper(DoRest,numberOfRows)
              -self.IGHelper(DoSow,numberOfRows)
              )
        return IG

    def IGHelper(self, action, nrOfRows):
        if(action == 0 or nrOfRows == 0):
            return 0
        else:
            return ((action/nrOfRows) * log2(action/nrOfRows))


    def toString(self, action):
        if action == AI.WalkEast:
            return "east"
        elif action == AI.WalkNorth:
            return "north"
        elif action == AI.WalkSouth:
            return "south"
        elif action == AI.WalkWest:
            return "west"
        elif action == AI.DoRest:
            return "rest"
        elif action == AI.DoHarvest:
            return "harvest"
        elif action == AI.DoSow:
            return "sow"




